package edu;

class MyUtils{

	
	static int ExponentiationMmodulo(int a, int k, int p){
		 int b=1;

		  while (k != 0) {
		    if (k % 2 == 0) {
		      k /= 2;
		      a = (a*a)%p;
		      }
		    else {
		      k--;
		      b = (b*a)%p;
		      }
		  }
		  return b;
	}
	
	static int LowestDenominator(int a, int b){
		
		while (a > 0 && b > 0){
		    if (a > b) a%=b;
		    else b%=a;
		}
		return a + b;
	}
	
	static int InversMod(int a, int b){
		
 		int U1=0,U2=1;
		int tmQ,tmB;
		int q;
		int cd = b;
		
		while (a!=1){
			tmQ=U2;
			tmB=a;
			
			q=b/a;
			
			
		    a=b%a;
		    b=tmB;
		    
		    U2=U1-q*U2;
		    U1=tmQ;
		    

		}
		
		return U2>0?U2:cd+U2;
	}

	
}